package Review;

public class Test38 {

	public static void main(String[] args) {
       int[] array={1,2,3,3,3,3,4,5};
       System.out.println(getNumberOfK(array, 3));
       System.out.println(new FindKNumber().getKNumber(array, 3));
	}
	public static int getNumberOfK(int[] array,int k){
		if(array==null||array.length==0){
			return 0;
		}
		int num=0;
		int first=getFirstK(array,0,array.length-1,k);
		int last=getLastK(array,0,array.length-1,k);
		if(first>-1&&last>-1){
			num=last-first+1;
		}
		return num;
	}
	public static int getFirstK(int[] array,int start,int end,int k){
		if(start>end){
			return -1;
		}
		int mid=(start+end)/2;
		if(array[mid]==k){
			if(mid==0||(mid!=0&&array[mid-1]!=k)){
				return mid;
			}
			else{
				return getFirstK(array, start, mid-1, k);
			}
		}
		else if(array[mid]>k){
			return getFirstK(array, start, mid-1, k);
		}
		else{
			return getFirstK(array, mid+1, end, k);
		}
	}
    public static int getLastK(int[] array,int start,int end,int k){
		if(start>end){
			return -1;
		}
		int mid=(start+end)/2;
		if(array[mid]==k){
			if(mid==array.length-1||(mid!=array.length-1&&array[mid+1]!=k)){
				return mid;
			}
			else{
				return getLastK(array, mid+1, end, k);
			}
		}
		else if(array[mid]>k){
			return getLastK(array, start, mid-1, k);
		}
		else{
			return getLastK(array, mid+1, end, k);
		}
		
	}

}

class FindKNumber{
	public int getFirstK(int []a, int k,int start,int end){
		if(start>end){
			return -1;
		}
		int middle = (start + end) / 2;
		if(a[middle] == k){
			if((middle > 0 && a[middle - 1] != k) || middle == 0){
				return middle;
			}
			end = middle - 1;
		}else if (a[middle] < k) {
			start = middle + 1;
		}else{
			end = middle - 1;
		}
		return getFirstK(a,k,start,end);
	}
	public int getLastK(int []a,int k,int start,int end){
		if(start>end){
			return -1;
		}
		int middle = (start + end) / 2;
		if(a[middle] == k){
			if((middle < a.length - 1 && a[middle + 1] != k) || middle == a.length - 1){
				return middle;
			}
			start = middle + 1;
		}else if (a[middle] < k) {
			start = middle + 1;
		}else{
			end = middle - 1;
		}
		return getLastK(a,k,start,end);
	}
	public int getKNumber(int []a,int k){
		if(a == null || a.length <= 0){
			return 0;
		}
		int num=0;
		int first = getFirstK(a, k,0 ,a.length - 1);
		int last = getLastK(a, k,0 ,a.length - 1);
		if(first > -1 && last > -1){
			num = last - first + 1;
		}
		return num;
	}
}